Search in Rotated Sorted Array（33-Medium）
Description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Solution
利用二分查找：O(log n)
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0)
return -1;
int l =0;
int r = nums.length - 1;
while(l <= r){
int m = (l + r) / 2;
if(target == nums[l])
return l;
if(target == nums[m])
return m;
if(target == nums[r])
return r;
if(target > nums[l] && target < nums[m]){
r = m - 1;
continue;
}else if(target > nums[m] && target < nums[r]){
l = m + 1;
continue;
}else if(nums[l] > nums[m]){
r = m -1;
continue;
}else if(nums[m] > nums[r]){
l = m + 1;
continue;
}
}
return -1;
}
}
优化：
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}
Find First and Last Position of Element in Sorted Array（34-Medium）
Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution
改进基本的二分查找：
在二分查找中基本的条件：
1）if(nums[mid] > target) right = mid -1;
2) if(nums[mid] < target) left = mid + 1;
3) if(nums[mid] = target) right = mid,找到目标值
在本题中查找first和last目标值，将分为两部分查找，先找first，再找 last。
1.Search first
first的查找应该使查找范围尽量靠左，尽管数组中可能有多个target，但是应该找到最左面的
[1,3,5,5,5,5,9], target = 5
l = 1; r = 9; mid = 5(2)；
mid == 5,这回应该尽量向左找，因为此时的5可能不是first，r = mid
l = 1; r = mid = 5; mid = 3;
mid < 5,这时时基本的二分查找条件，l = mid + 1
l = r = 5, 循环结束
2. Search last
和first相反，last应该使查找范围尽量靠右
同样的例子，[1,3,5,5,5,5,9], target = 5
l = 1; r = 9; mid = 5(2)；
mid == 5,这回应该尽量向右找，因为此时的5可能不是last，l = mid
l = mid = 5, r = 9, mid = 5(3)
mid = 5, 尽量向右找， l = mid
l = mid = 5 , r = 9 , mid = 5(4)
mid = 5 , 尽量向右找, l = mid
l = mid = 5, r = 9, mid = 5,----?
这时出问题了，最后的范围只剩下[5,9]但是取中值的时候，mid总是等于5，跳不出循环，
我们想让mid更靠右，因为last target 更在乎它右边的值，而first更在乎它左边的值，
但是 mid = (l + r）/ 2 的公式更偏向与左边，索引在找last的时候讲中值公式更改为 mid = (l + r）/ 2 + 1
索引最后一次 mid = 9
mid > 5,也就是说右边从这个值开始不会再有5了，而最后一个5在m - 1，r = m - 1
通过first, last 的差异来进行两次循环
solution 1：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] index = {-1,-1};
if(nums.length == 0)
return index;
int l = 0;
int r = nums.length - 1;
//第一次：找到第一个目标值索引
while(l < r) {
int m = (l + r) / 2;
if(nums[m] < target) {
l = m + 1;
}else {
r = m;
}
}
if(nums[l] != target) {
return index;
}else {
index[0] = l;
}
//第二次：找到最后一个目标值的索引
r = nums.length - 1;
while(l < r) {
int m = (l + r) / 2 + 1;
if(nums[m] > target) {
r = m - 1;
}else {
l = m;
}
}
index[1] = r;
return index;
}
}
solution 2
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] index = {-1,-1};
if(nums.length == 0) {
return index;
}
int left_index = Index(nums,target,true);
if(left_index == nums.length || nums[left_index] != target) {
return index;
}else {
index[0] = left_index;
}
index[1] = Index(nums, target,false) - 1;
return index;
}
public int Index(int[] nums, int target,boolean left) {
int l = 0;
int r = nums.length;
while(l < r) {
int m = (l + r) / 2;
if(nums[m] > target || (left && nums[m] == target)) {
r = m;
}else {
l = m + 1;
}
}
return l;
}
}
时间复杂度 O(log n)